#include "SeqList.h"

/**
 * 初始化顺序表
 * @param seqList
 */
void InitSeqList(SeqList *seqList) {
    seqList->datas = (ElementType *) malloc(sizeof(ElementType) * MAX_SIZE);
    seqList->length = 0;
}


/**
 * 输出顺序表
 * @param seqList
 */
void PrintSeqList(SeqList seqList) {
    for (int i = 1; i <= seqList.length; i++) {
        printf("%d\t%s\n", seqList.datas[i].key, seqList.datas[i].value);
    }
}


/**
 * 普通顺序查找,根据查找关键字 key 返回元素在顺序表中的位置,(从 1 开始,没找到就返回 0 )
 * @param seqList
 * @param key
 * @return
 */
int SearchSeqList(SeqList seqList, KeyType key) {
    for (int i = 1; i <= seqList.length; i++) {
        if (seqList.datas[i].key == key) {
            return i;
        }
    }
    return 0;
}


/**
 * 普通顺序查找,根据查找关键字 key 返回元素在顺序表中的位置,(从 1 开始,没找到就返回 0 )
 * 改进: 把带查找的关键字 key 存入表头(哨兵),从后向前逐个比较,可免去查找过程中每一步都见检测是否查找完毕,加快速度
 * @param seqList
 * @param key
 * @return
 */
int SearchSeqListGuard(SeqList seqList, KeyType key) {
    /* 把第一个位置的元素设置为哨兵 */
    seqList.datas[0].key = key;
    int i;
    /* 没有循环体的 for 循环
     * 原算法中 for 循环里面有一次判断,for 循环体内还会有以此判断
     * 改进算法中,我们只需要判断 key 值是否相等就可以了,省了 for 循环次数的判断
     * */
    for (i = seqList.length; seqList.datas[i].key != key; i--);
    return i;
}

/**
 *  二分查找 从 1 开始,找到就返回 找不见就返回 0
 * @param seqList 查找的顺序表
 * @param key 查找关键字
 * @return
 */
int SearchSeqListBinary(SeqList seqList, KeyType key) {
    int low = 1;
    int high = seqList.length;
    // 当 low <= high 进行循环
    while (low <= high) {
        // 折半
        int mid = (low + high) / 2;
        // 如果查找的关键字等于 顺序表折半元素的 key 就返回
        if (key == seqList.datas[mid].key) {
            return mid;
        } else if (key < seqList.datas[mid].key) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    // 查找失败
    return 0;
}

void TestSeqSearchList() {
    SeqList seqList;
    InitSeqList(&seqList);
    /* 查找的关键字 */
    int searchKey = 22;
    int keys[] = {10, 39, 22, 78, 3, 7, 48, 1};
    char *values[] = {"A", "C", "B", "E", "D", "H", "G", "F"};
    int len = sizeof(keys) / sizeof(keys[0]);

    for (int i = 1; i <= len; i++) {
        seqList.datas[i].key = keys[i - 1];
        seqList.datas[i].value = (char *) malloc(sizeof(char) * MAX_INFO_SIZE);
        strcpy(seqList.datas[i].value, values[i - 1]);
        seqList.length++;
    }/* for end */
    printf("初始化顺序表:\n");
    PrintSeqList(seqList);

    int pos = SearchSeqList(seqList, searchKey);
    printf("普通顺序表查找: \n\tsearchKey=%d\n\tpos=%d\n", searchKey, pos);


    /* 改进查找测试 */
    pos = SearchSeqListGuard(seqList, searchKey);
    printf("普通顺序表查找: \n\tsearchKey=%d\n\tpos=%d\n", searchKey, pos);
}
